Real-time systems differ from other forms of computing in that they must be temporally correct as well as logically correct. Such systems are developed to satisfy the following three primary criteria: guaranteed timing deadlines, fast response times, and stability in overload. Schedulability describes the capacity of a system. A system that is schedulable can meet all of its critical timing deadlines. Latency describes the responsiveness of a system. In a real-time system, it is the worst-case system response time to events that matters. Stability in overload means the system is able to meet its critical deadlines even if all deadlines cannot be met.
One of the most useful models available for developing real-time computing systems is Rate Monotonic Analysis (RMA). RMA provides a mathematical framework for reasoning about system timing behavior and provides an engineering basis for designing real-time systems. RMA was first disclosed in Liu & Layland, “Scheduling Algorithms for Multi-Programming in a Hard Real-Time Environment,” Journal of the Ass'n of Computing Machinery (ACM) 20, 1, 40-61 (January, 1973), incorporated by reference herein. Generally, Liu and Layland demonstrated that a set of n periodic tasks with deadlines at the end of their periods will meet their deadlines if they are arranged in priority according to their periods, and they meet a schedulability bound test. Since this paper, RMA has evolved into a collection of methods that have extended the original theory from its original form. The basic RMA real-time guarantee, however, has remained unchanged. For a general discussion of these collections of methods, see, for example, Klein et al, A Practitioner's Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-time Systems (Kluwer Academic Publishing, ISBN 0-7923-9361-9, 1993), incorporated by reference herein.
Methods currently exist to assess spare capacity and dynamically change the priority of tasks to alter the scheduling policy of the system. Spare capacity is the amount of execution time that can be added to the response of an event while preserving the schedulability of lower priority events. A related method, eliminating overrun, computes the amount of resource usage that must be eliminated to allow an event to meet its deadlines. See, Klein et al, A Practitioner's Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-time Systems, Chapter 4, Group 3 (Kluwer Academic Publishing, ISBN 0-7923-9361-9, 1993). Changing the priority of a task is used in various synchronization protocols to avoid priority inversion when multiple tasks share common data.
The validity of Rate Monotonic Analysis depends on preparing for the worst-case in terms of individual event timing and the concurrence of events. In other words, the system will be capable of meeting all of its deadlines if all worst-case events can be handled simultaneously. While mathematically certain, assuming worst-case timings and coincidences required by the RMA analysis may result in harsh feature/performance tradeoffs for the usually limited hardware computing capacity found in a typical real-time system. While the worst-case high priority event may occur very infrequently, the execution time for the worst-case high priority event must still be accounted for in RMA calculations. The capacity allocated to handle this rare worst-case event at high priority then gets traded off against the capacity available to lower priority events.
If RMA calculations show that the system is no longer schedulable with these maximum execution requirements, the designer is left with few options. Usually, the worst-case events will have to be redesigned to reduce their execution times. If the execution times cannot be reduced, the designer is left with discounting the offending event as an overload, provided the occasional timing violations to lower priority events can be tolerated. An overload condition is an acceptable alternative only if all lower priority events have soft deadlines (can tolerate a missed deadline occasionally). Unfortunately, this is rarely the case. In a system where such an overload situation exists, the real-time criteria of stability in overload is violated.
Currently, RMA only provides the tools necessary to determine if a system is schedulable. In other words, RMA will only tell you if a given design will work or not. For example, the method of assessing spare capacity is useful for determining how much execution time can be safely added to an event before timing requirements are broken. Likewise, RMA provides a method for determining how much execution time must be eliminated to meet timing requirements. These methods will prove useful for providing target values for redesign, but will not help if the execution times are intractable. There is no current method that allows a designer to gracefully handle intractable overloads.